﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class NegativeGraphDiv2
{
    public long findMin(int N, int[] s, int[] t, int[] weight, int charges)
    {
        int[, ,] step = new int[t.Length + charges + 1, N + 1, charges + 1];

        for (int v = 1; v <= N; v++)
        {
            for (int c = 0; c <= charges; c++)
            {
                if (v == 1 && c == 0) step[0, v, c] = 0;
                else step[0, v, c] = int.MaxValue/2;
            }
        }

        for (int i = 1; i <= t.Length + charges ; i++)
        {
            for (int v = 1; v <= N; v++)
            {
                for (int c = 0; c <= charges; c++)
                {
                    step[i, v, c] = int.MaxValue/2;
                    for (int j = 0; j < t.Length; j++)
                    {
                        int v1 = s[j];
                        int v2 = t[j];
                        int w = weight[j];
                        if (v != v2) continue;
                        if (c > 0)
                        {
                            step[i, v, c] = Math.Min(step[i - 1, v1, c - 1] - w, step[i, v, c]);
                        }
                        step[i, v, c] = Math.Min(step[i - 1, v1, c] + w, step[i, v, c]);
                    }
                }
            }
        }

        long min = long.MaxValue;
        for (int i = 1; i <= t.Length + charges ; i++)
        {
            for (int c = 1; c <= charges; c++)
            {
                min = Math.Min(step[i, N, c], min);
            }
        }
        return min;
    }
}

public class FixedDiceGameDiv2
{
    public double getExpectation(int a, int b)
    {
        double exp = 0.0;
        int sum = 0;
        for (int i = a; i > 1; i--)
        {
            sum += Math.Min(i - 1, b);
        }
        for (double i = (1.0) * a; i > 1; i--)
        {
            exp += (double)(i * Math.Min(i - 1, b) / sum);
        }
        return exp;
    }
}

public class SumOfPower
{
    public int findSum(int[] array)
    {
        int sum = 0;
        for (int i = 1; i <= array.Length; i++)
        {
            for (int j = 0; j < array.Length-i+1; j++)
            {
                for (int k = j; k < j + i; k++)
                {
                    sum += array[k];
                }
            }
        }
        return sum;
    }
}
